#include <memory>
#include <new>
#include <iostream>

/*
    std::destroy_at.... Need C++ 17
*/

namespace hamster
{
    template <typename T, typename Alloc = std::allocator<T>>
    class Vector
    {
        public:
        // Vector Type Traits
        using value_type = T;
        using allocator_type = Alloc;
        // Vector维护的是一个线性空间，因此迭代器类型就是指针，是std::random_access_iterator_tag
        using pointer = value_type *;
        using const_pointer = const value_type *;
        using iterator = value_type *;
        using const_iterator = const value_type *;
        using reference = value_type &;
        using const_reference = const value_type &;
        using size_type = size_t;
        using difference_type = std::ptrdiff_t;
        using reverse_iterator = std::reverse_iterator<value_type *>;
        using const_reverse_iterator = std::reverse_iterator<const value_type *>;

        // protected Allocator
        protected:
        // using data_allocator = std::allocator<T>;
        Alloc data_allocator;

        iterator start;
        iterator finish;
        iterator end_of_storage;

        void insert_aux(iterator position, const T &value);
        void deallocate()
        {
            if (start)
                data_allocator.deallocate(start, end_of_storage - start);
        }

        void fill_initialize(size_type n, const T &value)
        {
            start = allocate_and_fill(n, value);
            finish = start + n;
            end_of_storage = finish;
        }

        T* allocate_and_fill(size_type n, const T &value)
        {
            T *start = data_allocator.allocate(n);

            std::uninitialized_fill_n(start, n, value);

            return start;
        }

        public:
        iterator begin() {return start;}
        iterator end() {return finish;}
        size_type size() const {return finish - start;}
        size_type capacity() const {return end_of_storage - start;}
        bool empty() const {return begin() == end();}
        // dereference and return a reference
        reference operator[](size_type n) {return *(begin() + n);}
        const_reference operator[](size_type n) const {return *(begin() + n);}
    
        // constructor
        Vector() : start(nullptr), finish(nullptr), end_of_storage(nullptr) {}

        Vector(size_type n, const T& value) {fill_initialize(n, value);}

        explicit Vector(int n) {fill_initialize(n, T());}

        ~Vector()
        {
            for(std::size_t i = 0; i < finish - start; i ++)
            {
                // C++17
                std::destroy_at(&start[i]);
            }
            if(capacity() != 0)
            {
                deallocate();
            }
        }

        reference front() {return *begin();}
        // end() 返回的是最后一个元素之后的位置，back() 返回的是最后一个元素的位置
        reference back() {return *(finish - 1);}

        void push_back(const T& value)
        {
            if(finish != end_of_storage)
            {
                // C++ 20
                // std::construct_at(finish, value);
                // 等价于
                // ::new (static_cast<void*>(&*finish) T(value));
                ::new (static_cast<void*>(finish)) T(value);
                ++finish;
            }
            else
            {
                insert_aux(end(), value);
            }
        }

        void pop_back()
        {
            --finish;
            // C++17
            std::destroy_at(finish);
        }

        iterator erase(iterator position)
        {
            if(position + 1 != end())
            {
                std::copy(position + 1, finish, position);
            }
            --finish;
            std::destroy_at(finish);
            return position;
        }

        iterator erase(iterator first, iterator last)
        {
            iterator i = std::copy(last, finish, first);
            std::destroy(i, finish);
            finish = finish - (last - first);
            return first;
        }

        void resize(size_type new_size, const T& value)
        {
            if(new_size < size())
            {
                erase(begin() + new_size, end());
            }
            else
            {
                insert(end(), new_size - size(), value);
            }
        }

        void resize(size_type new_size) {resize(new_size, T());}
        void clear() {erase(begin(), end());}

        void insert(iterator position, size_type n, const T& value);
    };

    template <typename T, typename Alloc>
    void Vector<T, Alloc>::insert_aux(iterator position, const T &value)
    {
        if(finish != end_of_storage)
        {
            ::new (static_cast<void*>(finish)) T(value);
            ++finish;
            T value_copy = value;
            std::uninitialized_move(position, finish - 1, finish);
            *position = value_copy;
        }
        else
        {
            // No Space Left
            const size_type old_size = size();
            const size_type len = old_size != 0 ? 2 * old_size : 1;

            iterator new_start = data_allocator.allocate(len);
            iterator new_finish = new_start;
            try
            {
                new_finish = std::uninitialized_copy(start, position, new_start);
                ::new (static_cast<void*>(new_finish)) T(value);
                ++new_finish;
                new_finish = std::uninitialized_copy(position, finish, new_finish);
            }
            catch(const std::exception& e)
            {
                std::cout << e.what() << std::endl;
                std::destroy(new_start, new_finish);
                data_allocator.deallocate(new_start, len);
                throw;
            }

            std::destroy(begin(), end());
            deallocate();

            start = new_start;
            finish = new_finish;
            end_of_storage = new_start + len;
        }
    }

    template<typename T, typename Alloc>
    void Vector<T, Alloc>::insert(iterator position, size_type n, const T& value)
    {
        if(n != 0)
        {
            if(size_type(end_of_storage - finish) >= n)
            {
                // Left Space is Enough
                T value_copy = value;
                // 插入点之后的元素个数
                const size_type elems_after = finish - position;
                iterator old_finish = finish;
                if(elems_after > n)
                {
                    std::uninitialized_copy(finish - n, finish, finish);
                    finish += n;
                    std::copy_backward(position, old_finish - n, old_finish);
                    std::fill(position, position + n, value_copy);
                }
                else
                {
                    std::uninitialized_fill_n(finish, n - elems_after, value_copy);
                    finish += n - elems_after;
                    std::uninitialized_copy(position, old_finish, finish);
                    finish += elems_after;
                    std::fill(position, old_finish, value_copy);
                }
            }
            else
            {
                const size_type old_size = size();
                const size_type len = old_size + std::max(old_size, n);
                iterator new_start = data_allocator.allocate(len);
                iterator new_finish = new_start;
                try
                {
                    new_finish = std::uninitialized_copy(start, position, new_start);
                    new_finish = std::uninitialized_fill_n(new_finish, n, value);                
                    new_finish = std::uninitialized_copy(position, finish, new_finish);
                }
                catch(const std::exception& e)
                {
                    std::cout << e.what() << std::endl;
                    std::destroy(new_start, new_finish);
                    data_allocator.deallocate(new_start, len);
                    throw;
                }
                std::destroy(begin(), end());
                deallocate();
                start = new_start;
                finish = new_finish;
                end_of_storage = new_start + len;
            }
        }
    }
}
